﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CSharp.Study.Algorithm
{
    /// <summary>
    /// 给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
    ///（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
    /// </summary>
    internal class lc_01_两数之和
    {
        //输入：[3,2,4],6  返回值：[2,3]
        //说明：因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]
        public static void Go()
        {
            var arr = new int[] { 2, 11, 7, 9, 12 };
            var result = TwoSum(arr, 20);
            var result2 = TwoSumHash(arr, 20);
        }

        /// <summary>
        /// 暴力算法
        /// </summary>
        public static int[] TwoSum(int[] numbers, int target)
        {
            for (int i = 0; i < numbers.Length - 1; i++)
            {
                for (int j = i + 1 ; j < numbers.Length; j++)
                {
                    if (numbers[i] + numbers[j] == target)
                    {
                        return new int[] { i, j };
                    }
                }
            }
            return null;
        }

        public static int[] TwoSumHash(int[] arr, int target)
        {
            Dictionary<int, int> dic = new Dictionary<int, int>();//值 - 下标
            for (int i = 0; i < arr.Length; i++)
            {
                if (dic.ContainsKey(target - arr[i]))
                {
                    return new int[] { dic[target - arr[i]], i };
                }
                else
                {
                    dic.Add(arr[i], i);
                }
            }
            return null;
        }
    }
}
